package org.example;

import java.util.HashSet;
import java.util.Set;

public class Test1 {
    //leetcode 矩阵置零
    //https://leetcode.cn/problems/set-matrix-zeroes/description/?envType=study-plan-v2&envId=top-interview-150

    /**
     *
     * 使用hashset，set中存放为0元素的行坐标和列坐标
     * @param matrix
     */
    public void setZeroes2(int[][] matrix) {
        int n1 = matrix.length, n2 = matrix[0].length;
        //row存放为0的元素的行坐标，col存放列坐标
        Set<Integer> row = new HashSet<>();
        Set<Integer> col = new HashSet<>();
        for (int i = 0; i < n1; i++) {
            for (int j = 0; j < n2; j++) {
                if (matrix[i][j] == 0) {
                    if (!row.contains(i)) row.add(i);
                    if (!col.contains(j)) col.add(j);
                }
            }
        }
        for (Integer n : row) {
            for (int j = 0; j < n2; j++) {
                matrix[n][j] = 0;
            }
        }
        for (Integer n : col) {
            for (int i = 0; i < n1; i++) {
                matrix[i][n] = 0;
            }
        }

    }

    /**
     * 优化，用数组代替hashset
     * @param matrix
     */
    public void setZeroes1(int[][] matrix) {
        int n1 = matrix.length, n2 = matrix[0].length;
        //row存放为0的元素的行坐标，col存放列坐标
        int[] row = new int[n1];
        int[] col = new int[n2];
        for (int i = 0; i < n1; i++) {
            for (int j = 0; j < n2; j++) {
                if (matrix[i][j] == 0) {
                    row[i] = col[j] = 1;
                }
            }
        }
        for (int i = 0; i < n1; i++) {
            if (row[i] == 1) {
                for (int j = 0; j < n2; j++) {
                    matrix[i][j] = 0;
                }
            }
        }
        for (int j = 0; j < n2; j++) {
            if (col[j] == 1) {
                for (int i = 0; i < n1; i++) {
                    matrix[i][j] = 0;
                }
            }
        }
    }

    /**
     * 不额外创建连个数组记录为0的元素的行和列，而是直接使用矩阵的第一行和第一列来记录，那么如何记录呢
     * 我们通过修改第一行和第一列的数据，如果元素的值为0，那么就设置matrix[i][0] = matrix[0][j]
     * 这样就可以使用第一行和第一列来表示哪一行和哪一列的元素需要设置为0，所以我们i和j分别从1开始遍历元素
     * 但是这样的话，如果第一行和第一列中的元素也存在0的话该怎么办呢？我们可以先遍历第一行和第一列，
     * 然后分别用两个变量来记录第一行和第一列的元素是否需要设置为0
     * @param matrix
     */
    public void setZeroes(int[][] matrix) {
        int n1 = matrix.length, n2 = matrix[0].length;
        boolean flg1 = false, flg2 = false;
        //判断第一列中的元素是否存在0
        for (int i = 0; i < n1; i++) {
            if (matrix[i][0] == 0) {
                flg1 = true;
                break;
            }
        }
        //判断第一行中的元素是否存在0
        for (int j = 0; j < n2; j++) {
            if (matrix[0][j] == 0) {
                flg2 = true;
                break;
            }
        }
        //判断除了第一列和第一行之外的元素是否存在0，如果存在，就设置matrix[i][0] = matrix[0][j] = 0
        for (int i = 1; i < n1; i++) {
            for (int j = 1; j < n2; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = matrix[0][j] = 0;
                }
            }
        }
        //第二次遍历矩阵，如果matrix[i][0]或者matrix[0][j]为0，那么就表示该元素要设置为0
        for (int i = 1; i < n1; i++) {
            for (int j = 1; j < n2; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
        //最后判断第一行或者第一列是否需要设置为0
        if (flg1) {
            for (int i = 0; i < n1; i++) {
                matrix[i][0] = 0;
            }
        }
        if (flg2) {
            for (int j = 0; j < n2; j++) {
                matrix[0][j] = 0;
            }
        }
    }

    public static void main(String[] args) {
        Test1 test1 = new Test1();

    }
}
